package dfs

var (
	retArr = make([][]int, 0)
)

func dfs(nums []int, currentNumArr []int) {
	// 最后一个元素了，直接存入结果数组中，并退出
	if 0 == len(nums) {
		retArr = append(retArr, currentNumArr)
		return
	}
	// 通过一个map 登记当前位置遍历过的元素
	hasDfsNumMap := make(map[int]bool)
	for i := 0; i < len(nums); i++ {
		if !hasDfsNumMap[nums[i]] {
			newNumArr := make([]int, len(currentNumArr))
			copy(newNumArr, currentNumArr)
			newNumArr = append(newNumArr, nums[i])
			// 重新生成一个排序后的数组，注意要把选定的元素排除掉
			newBasicNumArr := make([]int, len(nums))
			copy(newBasicNumArr, nums)
			newBasicNumArr[i] = newBasicNumArr[len(newBasicNumArr)-1]
			newBasicNumArr = newBasicNumArr[:len(newBasicNumArr)-1]
			//sort.Ints(newBasicNumArr)
			dfs(newBasicNumArr, newNumArr)
			hasDfsNumMap[nums[i]] = true
		}
	}
}

func PermuteUnique(nums []int) [][]int {
	// 基本解法：深度遍历 + 记录剪枝
	retArr = make([][]int, 0)
	var initNumArr []int
	dfs(nums, initNumArr)
	return retArr
}
